// 给定一个单链表 L 的头节点 head ，单链表 L 表示为：

//  L0 → L1 → … → Ln-1 → Ln 
// 请将其重新排列后变为：

// L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

// 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
//当发现需要大量查找数据时使用数组进行缓存
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
    let res = head;
    let arr = [];
    while (res != null) {
        let p = res.next;
        res.next = null; //注意用数组进行缓存时要先将链表分割开来，这里要注意保存next的值
        arr.push(res);
        res = p;
    }
    let bef = 0;
    let aft = arr.length - 1;
    // 这里可以采用[bef, aft] = [0, arr.length - 1]的写法
    while (bef < aft) {
        arr[bef].next = arr[aft];
        // 注意防止为偶数时中间的两个节点形成循环
        bef + 1 !== aft && (arr[aft].next = arr[bef + 1]);
        bef++;
        aft--;
    }
    return arr[0]
};

//操作过于繁杂，而且容易出现next未定义的情况
var reorderList = function(head) {
    let res = head;
    let bef = head;
    let length = 0;
    let stk = [];
    while (res.next != null) {
        res = res.next;
        length++ //确定链表长度
    }
    let index = length / 2 == 0 ? length / 2 : length / 2 + 1;
    let befindex = 0;
    while (bef.next != null) {
        if (befindex > index) {
            stk.push(bef)
        }
        bef = bef.next;
        befindex++;
    }
    let res2 = head;
    length / 2 != 0 ? index++ : null;
    for (let i = 0; i < index; i++) {
        console.log(res2)
        res2.next = stk[stk.length - 1];
        stk.pop();
        res2 = res2.next;
    }
    return res2
};